import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        int[]array={1,9,2,8,3,7,4,6,5};
        mergeSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }

    private static void mergeSort(int[] array, int left, int right) {
        if(left>=right)
            return;
        int mid = left +(right-left)/2;
        mergeSort(array,left,mid);
        mergeSort(array,mid+1,right);
        int cur1 = left;
        int cur2 = mid+1;
        int[]tmp = new int[array.length];
        int i = 0;
        while(cur1<=mid&&cur2<=right){
            if(array[cur1]<array[cur2]){
                tmp[i++] = array[cur1++];
            }else{
                tmp[i++] = array[cur2++];
            }
        }
        while(cur1<=mid){
            tmp[i++] = array[cur1++];
        }
        while(cur2<=right){
            tmp[i++] = array[cur2++];
        }
        for (int j = left; j <=right ; j++) {
            array[j] = tmp[j-left];
        }
    }
}